Batch 2 - Class 49 - Graphs II

Preclass Exercise:

MartinShCol - 1.18 - My wife and I recently attended a party at which there were four other couples. Various handshakes took place. No one shook hands with himself/herself or with his/her spouse, and no one shook hands with the same person twice. After all handshakes were over, I asked each person, including my wife, how many hands he/she had shaken. They all gave me a different answer. How many hands did I shake?
Hint: Instead of 5 couples, solve for 2 couples, then for 3 and so on. See the patternAnswer: Since no one can shake more than 8 hands, and 9 people gave all different answers, their answers must be 0,1,2...8. The person who shook 8 hands must be married to a person who shook 0 hands (otherwise he could have shaken only 7 hands). Similarly, the person who shook 7 hands must be married to the person who shook 1 hand, and so on. The only person left, who shook 4 hands, is my wife. The graph below illustrates the pattern. It also shows that I shook 4 hands as well.

Attendance: Smiti, Muskaan, Praharsh, Liza, Nandini, Avy, Aryan, Shubham, Anisha, Hriday, Aastha, Adit and Diya on skype

Class Notes:

Friendship graph: Lets progressively build a graph of friendships. There are six people, and we will throw two dice to determine which pairs are friends. We will note them down.
How many pairs of friendship must exist,so that I can find a reference to any person?What is the largest number of friendships that may exist, and I still can't find a reference to someone?How can this be represented as a graph? Lets draw it, and now does answering the above questions become easier?How many pairs of friendship must exist, so that I can find a direct reference (one of my friends knows that person) to any person?

Review degree of vertices and edges. Draw some random graphs and let students discover that

Sum of degrees of all vertices is even
Sum of degrees of all vertices is twice the number of edges - explain why
Even sum implies that there have to be even number of odd-degree vertices
MC Chap 5 - Problem 11 - Can a kingdom in which 3 roads lead out of each city have exactly 100 roads?
Answer: No. For 100 roads, the sum of vertices must be 200, which is not divisible by 3
MC Chap 5 - Problem 14 - Can 9 line segments be drawn in the plane each of which intersects exactly 3 others?
What are the vertices and what are the edges here?Answer: No. With segments as vertices and intersections as edges, this means that odd number of vertices have odd number of edges.
MC Chap 5 - Problem 15 - There are 15 towns in a country, each of which is connected to at least 7 more. Show that you can get from any town to any other town.
Answer: Assume that you can't get from a given town to another. Then both of those must be disconnected, but each town connected to 7 other towns. Which would require at least 16 towns. But we have only 15, so the assumption that we can't get from a town to another can not hold.
Joke: How do make 7 even?
Subtract "s"
Joke: Why are the numbers 1-12 good security?
Because they are always on the watch!

Homework:

(Dudeney - 375) FIVE JEALOUS HUSBANDS. During certain local floods five married couples found themselves surrounded by water, and had to escape from their unpleasant position in a boat that would only hold three persons at a time. Every husband was so jealous that he would not allow his wife to be in the boat or on either bank with another man (or with other men) unless he was himself present. Show the quickest way of getting these five men and their wives across into safety. Call the men A, B, C, D, E, and their respective wives a, b, c, d, e. To go over and return counts as two crossings. No tricks such as ropes, swimming, currents, etc., are permitted.

References:

https://ia902701.us.archive.org/4/items/AmusementsInMathematicspdf/AmusementsInMathematics.pdf - Dudeney

Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg